class code5 {
    //进阶：类似KMP
    public boolean isSubsequence(String s, String t) {
        int n = t.length();
        int[][] dp = new int[n+1][26];//记录每个位置的上一个ch的位置
        for(char ch = 0;ch<26;ch++) {
            int p = -1;
            for(int i=0;i<=n;i++) { //从前往后记录dp
                dp[i][ch] = p;
                if(i<t.length() && t.charAt(i)==ch+'a') p=i;
            }
        }
        // 匹配
        int i = n;
        for (int j = s.length() - 1; j >= 0; j--) { // 跳跃遍历
            i = dp[i][s.charAt(j) - 'a'];
            if (i == -1) return false;
        }
        return true;
    }
}